/**
 * 给定一个二维01数组，只能向右或者向下走
 * 如果网格位置是1，则从左边进来只能向下走，从上边进来只能向右走
 * 问从左上到右下的方案总数
 * 加一个维度表示方向，令 Dijk 表示从起点到(i,j)位置且能够出k方向的方案总数
 * 根据(i,j)的取值进行计算即可
 */
using llt = long long;
llt const MOD = 1E9 + 7;
llt const None = -1;

int const RIGHT = 0;
int const DOWN = 1;

class Solution {

using vll = vector<array<llt, 2>>;

int N, M;
vector<vll> D;

public:
    int uniquePaths(vector<vector<int>>& grid) {
        N = grid.size();
        M = grid[0].size();
        D.assign(N, vll(M, {0LL, 0LL}));

        D[0][0] = {1LL, 1LL};
        for(int i=0;i<N;++i)for(int j=0;j<M;++j){
            if(0 == i and 0 == j) continue;

            if(0 == grid[i][j]){
                llt d = 0;
                if(i > 0){
                    d = (d + D[i - 1][j][DOWN]) % MOD;
                }
                if(j > 0){
                    d = (d + D[i][j - 1][RIGHT]) % MOD;
                }
                D[i][j] = {d, d};
            }else{
                if(i > 0){
                    D[i][j][RIGHT] = D[i - 1][j][DOWN];
                } 
                if(j > 0){
                    D[i][j][DOWN] = D[i][j - 1][RIGHT];
                }
            }
        }
        return D[N - 1][M - 1][DOWN];
    }
};